A path plan is to generate an available path from a given start point to a destination. The path plan is an important technology that is applied to various fields such as an autonomous drive of a moving robot, a motion generation of a game character, a road guide of a vehicle navigation system, and the like. One of the most important factors in the path plan is a search time. When the moving robot encounters an obstacle not displayed on a map, the path plan needs to be performed again. A long search time does not prevent the robot from running into an obstacle, and instead causes an unnatural operation (for example, pause and then move). In a game in which a plurality of characters appears, the above long path search time becomes a serious issue. When a path search time of a vehicle navigation system increases, a user may feel great inconvenience. Accordingly, there is a need for a fast path plan technology having a fast search speed.
In a mathematical aspect, a path plan issue becomes a graph search issue. In general, a graph search algorithm using a heuristic function such as A* algorithm is generally used. The graph search algorithm using the heuristic function initially searches a graph for a node close to a destination and thus, a search may be relatively quickly performed. When a searchable node is given as n and a destination node is given as t, one of frequently used heuristic functions is a lineal distance between two nodes as expressed by the following Equation 1.h(n,g)=√{square root over ((n·x−g·x)2+(n·y−g·y)2)}{square root over ((n·x−g·x)2+(n·y−g·y)2)}  [Equation 1]
Here, n·x denotes an x value of a current node, g·x denotes an x value of a destination node, n·y denotes a y value of the current node, and g·y denotes a y value of the destination node.
A searchable node close to a destination node based on a lineal distance using a heuristic function is initially visited. However, when a space to be searched is complex, a distance between the searchable node and the destination node may not be accurately expressed by the simple lineal distance. For example, when a detour needs to be performed due to a predetermined obstacle present between the searchable node and the destination node, the heuristic function using the lineal distance does not consider the obstacle and has a small value.